package 动态规划;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 最大子序和.java
 * @Description TODO
 * @createTime 2020年10月15日 20:14:00
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 示例:
 *
 * 输入: [-2,1,-3,4,-1,2,1,-5,4]
 * 输出: 6
 * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 *  dp[i]表示前i个数最大的连续子数组之和
    dp[i]=max{nums[i],dp[i-1]+nums[i]}
 */
public class 最大子序和 {
//    class Solution {
//        public int maxSubArray(int[] nums) {
//            int pre = 0, maxAns = nums[0];
//            for (int x : nums) {
//                pre = Math.max(pre + x, x);
//                maxAns = Math.max(maxAns, pre);
//            }
//            return maxAns;
//        }
//    }

}
